package com.liang.leetcode.binarytree.exercise;

import com.liang.leetcode.binarytree.entity.TreeNode;
import com.liang.leetcode.binarytree.util.BiTreeUtil;

import java.util.*;

/**
 * 222.完全二叉树的节点个数
 */
public class BiTree09_CountNodes {
    public static void main(String[] args) {
        // 创建一棵完全二叉树
        List<Integer> nodeList = Arrays.asList(1, 2, 3, 4, 5, 6);
        TreeNode root = BiTreeUtil.createBiTreeByRecursion(nodeList, 0);
        System.out.println("先序遍历：" + BiTreeUtil.preorderTraversal(root));
        // 节点个数
        System.out.println(countNodes3(root));
    }

    // 思路1：递归，后序遍历
    public static int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int countLeftNodes = countNodes(root.left);
        int countRightNodes = countNodes(root.right);
        return countLeftNodes + countRightNodes + 1;
    }

    // 思路2：迭代，层序遍历
    public static int countNodes2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int countNodes = 0;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                countNodes++;
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return countNodes;
    }

    // 思路3：用完全二叉树的特性
    // 根据左深度和右深度是否相同来判断该子树是不是满二叉树，满二叉树的结点数为：2^depth-1
    public static int countNodes3(TreeNode root) {
        if (root == null) {
            return 0;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        // 初始为 0，方便计算节点个数
        int leftDepth = 0, rightDepth = 0;
        // 求左子树的深度
        while (left != null) {
            left = left.left;
            leftDepth++;
        }
        // 求右子树的深度
        while (right != null) {
            right = right.right;
            rightDepth++;
        }
        // 完全二叉树的左右子树深度相等
        if (leftDepth == rightDepth) {
            // 相当于 2^leftDepth-1
            return (2 << leftDepth) - 1;
        }
        // 递归计算左右子树
        return countNodes3(root.left) + countNodes3(root.right) + 1;
    }

}
